14.7 KB · ⇊ 5 parts · ⤓ Micron 14.7 KB · ⤓ HTML 33.1 KB

top

Il mwawregistro a scorrimento a retroazione lineare (mwbain inglese mwbqlinear feedback shift register, mwbgLFSR) è una tipologia di mwbwregistri di traslazione i cui dati in ingresso sono prodotti da una mwcafunzione lineare dello stato interno.

Le uniche funzioni lineari di singoli mwcgbit sono lo mwcwXOR e lo XNOR (xor inverso); perciò è un mwdaregistro di traslazione i cui bit in ingresso sono prodotti dall'mwdqor esclusivo (xor) di alcuni bit memorizzati all'interno dei registri.

Il valore iniziale di un LFSR è chiamato mwdwseme, e poiché l'operazione del registro è mweadeterministica, la sequenza di valori prodotta dal registro è completamente determinata dal suo stato corrente o precedente. Allo stesso modo, poiché il registro ha un numero finito di stati possibili, prima o poi i valori in uscita si ripetono; ciò nonostante, un LFSR con una funzione di retroazione ben scelta può produrre una sequenza di bit che appare casuale ed ha un periodo molto lungo.

Applicazioni degli LFSR includono la generazione di mwegnumeri pseudo-casuali, mwewsequenze pseudo-rumore (approssimazione del mwfarumore bianco) e contatori digitali. Sono comuni implementazioni sia in mwfqhardware che in mwfgsoftware.

• Come funziona

• Proprietà della sequenza di uscita

• Applicazioni

• Possibile sostituto dei codici Gray

• LFSR di Galois

• Utilizzo in crittografia

• Funzioni combinatorie non lineari

• Generatori controllati dal clock

• Generatori a filtro

• Voci correlate

• Altri progetti

• Collegamenti esterni

La lista di posizioni dei bit che influenza lo stato successivo è detta mwggsequenza di tap. Nel diagramma sottostante, la sequenza è [16,14,13,11].

• Le uscite che influenzano l'ingresso sono dette mwhqtap (in blu nel diagramma sottostante).

• Un LFSR mwhwmassimale produce una mwiasequenza-n (cioè passa attraverso tutti i possibili stati del registro di traslazione tranne quello che produce tutti zeri), a meno che il suo stato iniziale non sia composto solo di zeri, nel qual caso l'uscita resta costante.

La sequenza di numeri prodotta da un LFSR può essere considerata un mwigsistema numerico binario valido quanto il mwiwcodice Gray o il codice binario naturale.

La sequenza di mwjqtap di un LFSR può essere rappresentata come un mwjgpolinomio mwjwmodulo 2. Questo significa che i coefficienti del polinomio devono essere 1 o 0. Questo è noto come mwkapolinomio di retroazione o mwkqpolinomio caratteristico. Ad esempio, se i mwkgtap sono al 16º, 14º, 13º e 11º bit (come sotto), il polinomio LFSR relativo è

x

11

+

x

13

+

x

14

+

x

16

+

1

{\displaystyle x^{11}+x^{13}+x^{14}+x^{16}+1}

Il termine noto del polinomio ("l'uno") non corrisponde a un mwlgtap; le potenze dei termini rappresentano i bit a mwlwtap, contando dalla sinistra.

• Se (e solo se) questo polinomio è mwmgprimitivo, allora l'LFSR è massimale

• L'LFSR sarà massimale solo se il numero di mwnatap è mwnqpari

• I valori dei mwnwtap in un LFSR massimale saranno mwoaprimi tra loro (due numeri si dicono primi tra loro se il loro mwoqmassimo comun divisore è 1)

• Ci può essere più di una sequenza di mwowtap che rende massimale un LFSR di lunghezza fissata

• Una volta trovata una sequenza di tap massimale, se ne può trovare un'altra con un procedimento automatico: se la sequenza di mwpqtap, in un LFSR a mwpgn bit, è [n,A,B,C], la sua sequenza "speculare" è [n,n-A,n-B,n-C] (ad esempio la sequenza [32,3,2,1] ha come controparte [32,31,30,29]). Entrambe producono un LFSR massimale.

• Uni e zeri si susseguono in mwrgcorse (runs). La sequenza di uscita 0110100, ad esempio, è composta da cinque corse di lunghezza 1,2,1,1,2, rispettivamente. In un periodo di un LFSR massimale, appaiono mwrw 2 n − − 1 {\displaystyle 2^{n-1}} corse (ad esempio, un LFSR a 6 bit avrà 32 corse); esattamente mwsa 1 / 2 {\displaystyle 1/2} di queste corse saranno di un bit, mwsq 1 / 4 {\displaystyle 1/4} di 2 bit, fino ad un'unica corsa di mwsg n − − 1 {\displaystyle n-1} bit a zero, ed un'unica corsa di mwsw n {\displaystyle n} bit a uno. Questa stessa proprietà ci si aspetterebbe in una sequenza veramente casuale.

• Le sequenze di uscita degli LFSR sono mwtqdeterministiche: se si conosce lo stato attuale, si può prevedere il prossimo. Questo non è possibile in eventi veramente casuali come il mwtgdecadimento radioattivo.

Gli LFSR possono essere implementati in hardware, e ciò li rende utili in applicazioni che richiedono la generazione molto rapida di numeri pseudo-casuali, come nella tecnica radio mwuqDirect Sequence Spread Spectrum, usata ad esempio nell'mwugUMTS.

Il mwvaGlobal Positioning System (GPS) usa gli LFSR per trasmettere rapidamente una sequenza che indica degli istanti relativi ad alta precisione, sfruttandone il determinismo: basta infatti trasmettere il seme utilizzato nel trasmettitore e la sequenza generata sarà identica anche sul ricevitore.

Alcune applicazioni hanno bisogno di marchiare delle singole posizioni ad una certa distanza con valori unici. Ad esempio, molti mwvwmetri segnano ogni centimetro con un numero unico usando il mwwasistema metrico decimale. Quando gli indici e le posizioni devono essere comprensibili ad una macchina, sono spesso marchiate usando sequenze LFSR, in quanto i contatori LFSR sono i più semplici e veloci tra i contatori binari, anche più dei contatori basati su mwwqcodice Gray. Data una sequenza di output è possibile costruire un LFSR di dimensione minima usando l'algoritmo Berlekamp-Massey.

Un LFSR di mwxqGalois, o un LFSR in configurazione di Galois, è una variante dello schema classico degli LFSR.

Nella configurazione di Galois, quando il sistema è soggetto a mwxwclock, i bit che non sono mwyatap sono traslati come di consueto; dei mwyqtap, invece, si fa lo XOR con la nuova uscita, e il risultato poi diventa il nuovo ingresso.

Gli LFSR di Galois non concatenano ogni mwywtap per produrre il nuovo ingresso, perciò è possibile calcolare i mwzatap in parallelo, aumentando così la velocità di esecuzione: l'operazione di XOR è realizzata nell'LFSR e non ci sono XOR in serie, perciò i tempi di propagazione si riducono a quelli di uno XOR invece di quelli di una catena degli stessi.

Gli LFSR sono componenti molto utilizzati nei mwbacifrari a flusso come generatori di mwbqnumeri pseudo-casuali, perché possono essere facilmente ed economicamente implementati in mwbghardware e possono all'occorrenza essere analizzati matematicamente. L'uso degli LFSR da soli, però, è insufficiente a fornire una buona sicurezza. Molti schemi sono stati proposti per incrementare la sicurezza degli LFSR.

Poiché gli LFSR sono intrinsecamente lineari, una tecnica per rimuovere la linearità consiste nell'applicare ai risultati di più LFSR in parallelo una funzione booleana non lineare e formare un mwcqgeneratore di combinazioni. Diverse proprietà di queste mwcgfunzioni combinatorie sono critiche per assicurare la sicurezza dello schema risultante, ad esempio, in modo da evitare attacchi basati sulla mwcwcorrelazione.

Normalmente gli LFSR eseguono passi regolari. Un approccio per introdurre delle non-linearità consiste nell'usare per lo LFSR un mwdgclock irregolare, controllato dall'uscita di un secondo LFSR. Tali generatori comprendono il generatore stop-and-go, il generatore a passo alternato e il generatore a rimpicciolimento.

Il mweageneratore stop-and-go (Beth and Piper, 1984) è composto da due LFSR. Un LFSR ha un colpo di clock se l'uscita del secondo è un "1", altrimenti ripete la sua uscita precedente. Questa uscita è poi (in alcune versioni) combinata con l'uscita di un terzo LFSR con clock regolare.

Il mweggeneratore a rimpicciolimento ha un approccio differente. Usa due LFSR, entrambi con clock regolare. Se l'uscita del primo LFSR è "1", l'uscita del secondo LFSR è l'output del generatore. Se il primo LFSR produce uno "0", però, l'uscita del secondo è scartata, e il generatore non produce bit. Questo meccanismo è vulnerabile agli attacchi temporizzati sul secondo generatore, poiché la velocità dell'output è variabile in dipendenza dello stato del secondo generatore. Questo problema può essere alleviato mantenendo una porzione dell'uscita in un mwewbuffer.

Un altro approccio per migliorare la sicurezza di un LFSR è passare l'intero stato di un LFSR ad una mwfgfunzione di filtraggio non lineare.

• mwggSequenza di lunghezza massima

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul registro a scorrimento a retroazione lineare

• mwhw(EN) Tabella degli LFSR massimali di lunghezza da 3 a 168 bit (PDF), su xilinx.com.

• mwiq(EN) Procedura per la generazione di numeri pseudo-casuali, su maxim-ic.com. URL consultato il 20 maggio 2006 (archiviato dall'url originale il 25 dicembre 2008).

• mwiw(EN) ee.ualberta.ca, https://web.archive.org/web/20080919171943/http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html Titolo mancante per url urlarchivio (aiuto) (archiviato dall'url originale il 19 settembre 2008).

• mwjg(EN) quadibloc.com, http://www.quadibloc.com/crypto/co040801.htm Titolo mancante per url url (aiuto).

• mwkq(EN) Semplice spiegazione degli LFSR per ingegneri, su yikes.com. URL consultato il 20 maggio 2006 (archiviato dall'url originale il 15 marzo 2006).

• mwkw(EN) Termini di retroazione, su ece.cmu.edu.

• mwlq(EN) Teoria generale degli LFSR, su homepage.mac.com. URL consultato il 20 maggio 2006 (archiviato dall'url originale il 5 giugno 2001).

• mwlw(EN) Tabelle delle sequenze di tap massimali, su homepage.mac.com. URL consultato il 20 maggio 2006 (archiviato dall'url originale il 20 giugno 2001).